1. Technical Field
The invention relates to medium access control (MAC) layer design and data modulation in a communication system. The invention also relates to any scenario where resources that can be represented numerically are shared and an allocation scheme is subsequently required. The medium access control (MAC) layer is responsible for managing channel access for communicating parties.
2. Description of the Prior Art
There are three general approaches to providing access to multiple users of a communication system:    1. Divide the channel by time, frequency, code, or a combination and allocate the channel slices to the communicating parties either statically or dynamically. Examples of this application include Code Division Multiple Access (CDMA) and Time Division Multiple Access (TDMA) algorithms.    2. Let the users compete (listen) for the channel, transmit when the channel is quiet, look for acknowledgements from receiver to determine whether the data has been transmitted without error, and retransmit when a collision occurs. Carrier Sense Multiple Access with collision avoidance (CSMA-CA), which is the basis of Ethernet communications, is an example of this approach.    3. A combination of approaches 1, and 2, above. Slotted Aloha is an example of this approach.
Abramson (N. Abramson, The Aloha System—Another Alternative for Computer Communications, Proceedings of Fall Joint Computer Conference, AFIPS Conference, 1970 http://www.isoc.org/internet/history/brief.shtml) invented Aloha and its more efficient variation, Slotted Aloha. In Slotted Aloha, the transmitters reserve a slot in the reservation time and then transmit in the reserved slot. When there is more than one transmitter, contentions in the reservation time happen. The contention is resolved by having the transmitter first listening to the channel and, if channel is not available, then waiting a random time before requesting for a reserved slot.
When it comes to low-power efficient interrogation with low complexity, Radio Frequency Identification (RFID) technology is a natural application and a direct beneficiary. The first two generations of RFID, i.e. Gen-0 and Gen-1, use the third approach outlined above by applying binary tree search algorithms to identify all tags in the vicinity of an interrogator. The following steps are used by the algorithm:                1. An interrogator broadcasts a wake-up message.        2. All tags wake up and energize themselves.        3. The interrogator starts an inventory round.        4. All tags respond; if only one tag responds, there is no collision; otherwise, there are collisions.        5. The interrogator detects the collisions and starts a binary search algorithm to isolate all tags.        
The binary search algorithm is as follows:
1. The interrogator asks all tags whose least significant bit (LSB) is a binary “0” to transmit; if no or one tag responds, then the interrogator moves to the other branch by asking all tags whose LSB is a “1” to transmit.
2. If a collision occurs, the interrogator branches and asks all tags whose LSB is “00” to transmit.
In this manner the algorithm reaches all leaves and can isolate and read all tags.
As is apparent, this algorithm is very inefficient when there are many tags. A variation of this algorithm tries to do a more efficient search. Still, this approach cannot exhibit high performance when employed in massive interrogation with a physical layer based on narrowband backscattering. It requires at least two downlink messages per tag, which renders it inefficient.
The following work has proposed variations to the above algorithms:
In Tervoert et al. (U.S. Pat. No. 5,124,699 Jun. 23, 1992 Tervoert et al.) the tags are in contention for the channel and, based on the frequency of the interrogation field (transmitted signal from interrogator), the tags either transmits or temporarily deactivates itself for a period of time.
In Vercelloti et al. (U.S. Pat. No. 5,266,925 Nov. 30, 1993 Vercellotti et al.) the contention is broken by an address that is sent by interrogator. Those tags that have an address greater the transmitted address respond. If there is more than one response, then the interrogator transmits an address that is greater than previous one. This process continues until only one tag responds.
In Scop et al. (U.S. Pat. No. 5,390,360 Feb. 14, 1995 Scop et al.) the transmitters all wait for different random delay and, at the end of the delay, they check to make sure that the channel is silent before transmitting their information. This is a variation of CSMA-CA.
In Huber (U.S. Pat. No. 5,410,315 Apr. 25, 1995 Huber) the transmitters are selected based on their group associations. The interrogator chooses a group. All transmitters that belong to that group transmit their information. If there is more than one member to the group, the interrogator chooses a subgroup of the group. This process continues until only one transmitter responds.
In Snodgrass et al. (U.S. Pat. No. 5,365,551 Nov. 15, 1994 Snodgrass et al.) each transmitter chooses a random number from a known range and transmits it to the interrogator. The interrogator then uses that number to link to each transmitter. If there is more than one transmitter, the interrogator has to request a subset of the transmitters to transmit their random number to avoid a collision.
In Orthmann et al. (U.S. Pat. No. 5,489,908 Feb. 6, 1996 Orthmann et al.) Each transmitter is assigned a unique identification code. The interrogation unit dynamically constructs and modifies a bit string used to solicit responses from selected transmitters until each transmitter is identified. The bit string is transmitted to the transmitters, which compare it with the least significant bits of their respective identification codes. A mismatch between the identification code and the bit string results in suppressing the response from the transmitter.
In Shanks et al. (U.S. Pat. No. 7,212,125 May 1, 2007 Shanks et al.) they propose a binary traversal communications protocol. In this protocol, the interrogator uses a binary search algorithm, very similar to Orthmann et al. (infra) to isolate and provide a free channel to a transmitter.
In Reynolds et al. (U.S. Pat. No. 6,286,762 Sep. 11, 2001 Reynolds et al.) the search for potential transmitters is started from a list of possible transmitters that the interrogator holds. The interrogator then performs either an inclusive or exclusive search to ascertain the presence of the transmitters that are on the list, and the possible presence of other transmitters which are not on the list.
In Bandy et al. (U.S. Pat. No. 6,002,344 Dec. 14, 1999 Bandy et al.) A tag interrogator transmits a wake-up signal followed by at least one clock signal. Each tag increments a first tag count in response to the clock signal, and transmits the Tag ID assigned to the tag when the first tag count corresponds to the Tag ID assigned to the tag. The tag interrogator records the transmitted Tag IDs. When more than one tag transmits simultaneously, the tag stores the Tag ID to resolve contention when the first read cycle is complete. In the second read cycle, the tag interrogator transmits the contended Tag ID followed by at least one clock signal. Each tag that contended for the transmitted Tag ID increments a second tag count in response to the clock signals, and transmits the manufacturer number assigned to the tag when the second tag count corresponds to the manufacturer number assigned to the tag. The tag interrogator records the transmitted Tag IDs, completing the inventory of the tags.
RFID Gen-2 MAC layer is a variation on Time Division Multiple Access, which uses a counter instead of a clock. Each tag choose a counter number randomly, from 0 to 2n−1 where n is an integer from 1 to 15 and is broadcast by the interrogator. The tag counter is incremented upon reception of a special increment command from the interrogator. In case of a collision, the increment command causes the tag that has just transmitted to choose another random number.
The steps are as follows:                1. The interrogator broadcasts a wake-up message.        2. All tags wake up and energize themselves.        3. The interrogator starts an inventory round.        4. All tags respond; if only one tag responds, there is no collision; otherwise, there are collisions.        5. In case of collision, this interrogator transmits a number n.        6. All tags compute a random number between 0 and 2n−1 for their slot number.        7. Tags that have the 0th slot number transmit their IDs.        8. If no collision, the interrogator sends an ACK and an increment command:        9. All tags that have not transmitted yet, increment their counter number and, if it is equal to their slot number, they transmit their ID;        10. All tags that have transmitted in this inventory round go to sleep for the next round.        
If collisions occur, the interrogator detects the collision and sends an increment without an ACK:                a. All tags that have not transmitted yet increment their counter number and, if it is equal to their slot number, they transmit their IDs;        b. All tags that have transmitted but not received an ACK prior to increment, compute another random slot number.        
This MAC layer algorithm is also inefficient, because it requires at least two messages for every Tag i.e. maximum efficiency is around 50%. Another important source of inefficiency that is often not reflected in the logical operation of the MACs based on full-duplex communication is the Tx-Rx switching overhead.
IEEE 802.15.4 is the standard for low data rate Personal Area Network (PAN) communication systems, while IEEE 802.15.4a specifies the physical and MAC layers for an ultrawide band (UWB) PAN communication system. At the physical layer, the latter specifies an ultrawide band impulse radio (UWB-IR) with direct sequence spreading with differential BPSK modulation of chips. At the MAC layer, it recommends using either slotted or unspotted algorithms.
For both systems, Carrier Sense Multiple Access with Collision Avoidance (CSMA-CA) is used. Each transmitter, when it has data to transmit, scans the channel: If the channel is quiet, the transmitter transmits its data. If the channel is busy, the transmitter backs-off, based on some predetermined algorithm, e.g. negative exponential, starts a timer and, when the timer expires, again scans the channel for activities. In the slotted version, all participants are synchronized to an external beacon. In the unslotted version, the devices are not synchronized and the starts of the back-off periods are not aligned.
Mertz and Boudec (Ruben Merz, Jorg Widmer, Jean-Yves Le Boudec, and Bozidar Radunovic, “A Joint PHY/MAC Architecture for Low-Radiated Power TH-UWB Wireless Ad-Hoc Networks”, School of Computer and Communication Sciences, EPFL, 2004 http://infoscience.epfl.ch/getfile.py?docid=5370&name=MerzWLBR05&format=pdf& version=1) propose a rate-controlled, time-hopping ultrawide band (TH-UWB) transmitter. Their proposal requires both the transmitter and the receiver to time-hop at the same rate and both to be able to listen to the channel to make sure that it is not occupied by other transmitters.
In communications, modulating is the process of embedding information into a medium that can be transmitted and received. Normally a carrier is used as the medium channel selector and it is then modulated with the data through manipulation of the medium resources. The manipulated carrier is transmitted and the receiver at the other end demodulates the data and recovers the information by observing the changes in the manipulated resource.
For example, the frequency of a carrier can be varied as a function of the bits of information to be transmitted. Subsequently, the data is modulated on the carrier as variations of its frequency. Time is an omnipresent resource. Others are, but not limited to, frequency and its parameters, i.e. phase and amplitude, medium characteristics such as viscosity, density, transparency, etc. Even codes and symbol constellations can be used as medium resources. In principle, any parameters that can be changed in the medium to deliver information can be considered as a medium resource and may be altered to convey information. Time-domain radio communication, e.g. UWB Impulse Radio, uses impulses without a continuous carrier although the impulse itself may oscillate in its duration. However, most continuous wave modulations apply to UWB-IR technology as well.
The most common methods of modulation are frequency, phase, and amplitude modulation, and hybrids such as Quadrature Amplitude Modulation (QAM). A particularly easy modulation technique that lends itself well to UWB systems and fiber medium is Pulse Position Modulation (PPM) which states the binary state of an impulse based on its position inside its timeslot. In a PPM approach, the position of the pulse inside a slot determines its binary value. In 13.56 MHz frequency vicinity cards (ISO 15693 standard), the number of these positions can be 1 out of 4 or 1 out of 256. It is noteworthy that this approach is a pure modulation technique and does not address the multi-access problem.
An important characteristic of all of these technologies is that the process of modulation is distinctively separate from the process of Multi-Access. Multi-access techniques are used for finding room in the medium and modulation is used to convey data by manipulating medium resources.
The data transmission rate of a link can be increased by compression prior to transmission and decompression upon reception of the data. This compression mechanism is not an integral part of a MAC layer and is performed in a separate stage.
Higher data rates often mean a higher system performance, but also impact power dissipation, signal integrity, range, and device complexity.
It is desirable to have a MAC solution that performs optimally for any given application, especially when the system is under severe constraints in terms of power, cost, performance, and complexity. An example of such a constrained communication system is the Radio Frequency Identification (RFID). A basic RFID system is normally composed of a number of tags responding to an interrogating reader. Passive RFID tags are energized by the incident electromagnetic signals propagated by the reader, while active and semi-active tags, respectively, rely on integral power sources or a combination of the acquired and integral energy. A passive responder is consequently under extreme power constraints. It must receive enough RF energy from a distance useful to the application to power up its circuitry, normally composed of computational, memory and transmitter units. Furthermore, RFID tags are typically involved in inventory rounds in which many tags are simultaneously interrogated by a reader in a short snap. In a dynamic case, e.g. when the tags and the interrogator (the reader) are moving relative to one other, depending on the speed of the movement and the number of tags, the duration of an inventory round is increasingly important. That is, much time cannot be devoted to resolving the many collisions in the process of interrogating the tags. A typical example of this case is at point of sales (PoS). The typical scenario for PoS is that the entire content of a customer cart needs to be scanned quickly and robustly. Once the cart is driven outside the range of the reader, the window of opportunity to scan the cart is closed, which makes a quick and massive inventory scan crucial.
Even in the case of more relaxed constraints, as in conventional RF data communication and active RFID applications, low power dissipation and high data rate in a massively populated network is desirable.